package com.dhu.graph.commonGrpaph.cycleAndBinary;

import com.dhu.graph.basic.GraphImpls.Graph;

/**
 * @Author ：snow
 * @Date ：Created in 2020-04-23
 * @Description： 一个图是否存在环
 * @Modified By：
 * @Version:
 */
public class Cycle {
    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph G){
        this.marked = new boolean[G.getVertexes()];
        for (int i = 0; i < G.getVertexes(); i ++){
            if(!marked(i)){
                dsf(G,i,i);
            }
        }
    }


    private boolean marked(int v){
        return marked[v];
    }

    /**
     * 搜索到某一个顶点出现环的条件如何理解：在搜索遍历过该顶点的临接表时，会逐个的标记该邻接表的中的顶点，
     * 如果出现环，那么在递归遍历该临接表中某一顶点的邻接表时，当前顶点的临接表中的某一个顶点会被标记，当遍历到该邻接表的当前顶点
     * 发现已近被别人标记，于是判断，这个顶点是不是它本身，如果不是，说明已经有一条路径从它自身出发走到了这个已近被别人（更深层的递归）标记了的
     * 顶点处，自身和这个被别人已经标记了的顶点有本来存在一条边， 于是证明，存在环。是本身的情况：由于顶点本身也在他邻接表中的顶点的邻接表
     * 中，自然在遍历它的临接表中的顶点的邻接表时会访问到它，算是一种走回头路的情况，不能算是绕了一圈回来。
     * @param G
     * @param v
     * @param u 路径上v的上一个顶点
     */
    private void dsf(Graph G, int v, int u){
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            if(!marked[w])
                dsf(G, w, v);
            else if(w != u) hasCycle = true;
        }
    }
    public boolean hasCycle(){
        return hasCycle;
    }
}
